/**
 * 10. 正则表达式匹配
 * https://leetcode-cn.com/problems/regular-expression-matching/
 */

const star = '*';
const dot = '.';

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
function isMatch(s, p) {
  const sLen = s.length;
  const pLen = p.length;
  const sMatchLen = sLen + 1;
  const pMatchLen = pLen + 1;
  // 第一个字符必须为空字符串，以便 base case 能顺利计算
  const sMatchChars = ['', ...s.split('')];
  const pMatchChars = ['', ...p.split('')];
  // 动态规划二维表格，将其中的数据初始化为 false
  const dp = new Array(sMatchLen);
  for (let i = 0; i < sMatchLen; i += 1) {
    dp[i] = new Array(pMatchLen).fill(false);
  }
  // 初始化 base case
  dp[0][0] = true; // 源字符串和匹配字符串都为空串时肯定匹配
  for (let j = 1; j < pMatchLen; j += 1) {
    // 因为空字符串和正则的匹配需要分情况讨论，如果带有 * 号则代表这个星号和前面的字符可以被去除再进行字串的匹配
    // 因此当前位置如果是 * 号就可以看星号前面两个字符的子串是否匹配
    if (pMatchChars[j] === star) {
      dp[0][j] = dp[0][j - 2];
    }
  }
  // 开始进行动态规划表格的正式填充
  for (let i = 1; i < sMatchLen; i += 1) {
    for (let j = 1; j < pMatchLen; j += 1) {
      const curSChar = sMatchChars[i];
      const curPChar = pMatchChars[j];
      // 情况 1.0.0：当前串末尾的字符是相互匹配的，那么这两个串最终是否匹配要看双方的前一个位置的字串是否匹配
      if (curSChar === curPChar || curPChar === dot) {
        dp[i][j] = dp[i - 1][j - 1];
      }
      // 情况 2.0.0：p 串的末尾是 * 号
      else if (curPChar === star) {
        const prePChar = pMatchChars[j - 1];
        // 如果 p 串 * 号前的子串和当前 s 串是情况 1.0.0，那么此时有三种情况都可以使当前串最终匹配
        if (curSChar === prePChar || prePChar === dot) {
          dp[i][j] =
            // 消除掉当前 p 串的最后两个字符（x*）和 s 串的最后一个字符（x），如果此时两者子串匹配那当前串也匹配
            dp[i - 1][j - 2]
            // 只单纯消除 s 串的最后一个字符，如果剩余的 s 子串也和当前的 p 串匹配那当前串也匹配
            || dp[i - 1][j]
            // 还可以消除掉当前 p 串的最后两个字符（x*）当它不存在看看剩余的 p 子串是否和当前 s 串匹配
            || dp[i][j - 2]
          ;
        }
        // 如果不符合 1.0.0 的情况也不要紧，可以消除掉 p 串的最后两个字符（x*）看看剩余的 p 子串是否和当前 s 串匹配
        else {
          dp[i][j] = dp[i][j - 2];
        }
      }
    }
  }
  return dp[sLen][pLen];
}

console.log(isMatch('aa', 'a') === false);
console.log(isMatch('aa', 'a*') === true);
console.log(isMatch('ab', '.*') === true);
console.log(isMatch('aab', 'c*a*b') === true);
console.log(isMatch('mississippi', 'mis*is*p*.') === false);
